/**
 * 
 */
package dp;

import java.util.Stack;

import utils.CreateUtils;
import utils.PrintUtils;
/**
 * @author Michael
 *
 * http://tech-queries.blogspot.com/2011/03/maximum-area-rectangle-in-histogram.html
 */
public class MaxRectangeAreaInHistogram {

	
	// widths[i]: the maximum width of rectangle containing the i-th histogram
	// widths[i] = leftOffset + rightOffset + 1
	// h[i-leftOffset] is the leftmost histogram whose height is at least h[i]
	// answer: max(h[i]*width[i])
	// complexity: O(2n), O(n)
	public static int maxArea(int[] h) {
		assert (h != null);
		
		int[] width = new int[h.length];
		int[] left = new int[h.length];
		int[] right = new int[h.length];
		Stack<Integer> s = new Stack<Integer>();
		
		// find the leftOffset for all histogram
		for (int i = 0; i < h.length; ++i) {
			while (!s.isEmpty() && h[s.peek()] >= h[i]) {
				s.pop();
			}
			int leftOffset = s.isEmpty() ?  i : i - 1 - s.peek();
			width[i] = leftOffset;
			left[i] = i - leftOffset;
			s.push(i);
		}
		
		s.clear();
		// find the righOffset for all histogram
		for (int i = h.length - 1; i >= 0; --i) {
			while (!s.isEmpty() && h[s.peek()] >= h[i]) {
				s.pop();
			}
			int rightOffset = s.isEmpty() ? h.length - 1 - i : s.peek() - 1 - i;
			width[i] += rightOffset + 1;
			right[i] = i + rightOffset;
			s.push(i);
		}
		
		int max = Integer.MIN_VALUE;
		int maxLeft = -1;
		int maxRight = -1;
		for (int i = 0; i < h.length; ++i) {
			int area = h[i] * width[i];
			if (area > max) {
				max = area;
				maxLeft = left[i];
				maxRight = right[i];
			}
		}

		System.out.println("start: " + maxLeft + " end: " + maxRight);
		return max;
	}
	
	/**
	 * 
	 */
	public MaxRectangeAreaInHistogram() {
		// TODO Auto-generated constructor stub
	}

	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] h = CreateUtils.randNonNegIntArray(10, 10);
		for (int i = 0; i < h.length; i++)
			h[i]++;
		PrintUtils.printArray(h);

		System.out.println(maxArea(h));

	}

}
